I. Field of the Invention
The present invention relates to electronic circuits. More particularly, the present invention relates to a novel and improved method and apparatus for reducing the RAM requirement in a device while maintaining fast look up and retrieval of data from slow non-volatile memory.
II. Description of the Related Art
Electronic memory of some type is used in almost all modem electronic devices. Electronic memory can take the form of floppy discs, magnetic tape, hard discs, and integrated circuits (IC). Each form of memory has its advantages and disadvantages. Floppy discs allow numerous data updates on a portable medium but have limited capacity and extremely long read and write access times. Both magnetic tape and hard discs have the capability for enormous capacity but are not portable, require large amounts of support hardware, and have slow read and write access times. Data saved in floppy disc, hard disc, and magnetic tape is often first formatted in software to a file format prior to saving on the medium. When data is recovered from the storage medium the software file routine must be run to locate and extract the requested data. This further slows the data access process because it adds a software layer on top of the already slow hardware access.
IC memory is typically used where memory needs to be integrated into a portable device. Varying the type and number of ICs can scale the amount of memory. ICs require minimum support hardware, are extremely small, and can provide fast read and write access times. Some IC memory can easily support direct access without the need for a software layer.
Numerous different types of IC memory are available to provide solutions to various design requirements. Each type of memory is able to satisfy a number of design requirements, but no one memory type is able to provide a complete design solution. The type of memory chosen for any particular application will depend on planned usage and performance design trade-offs.
The most common type of IC memory is Read Only Memory (ROM). As the name implies, the memory is only read accessible. A ROM device cannot be rewritten once it has been programmed. Embedded software applications use ROM to store embedded code and data records. The processor in an embedded software application retrieves each instruction from ROM and executes it. Different types of ROM are available depending on the volatility of the information to be programmed within the ROM. If the information to be stored in ROM is not expected to change and the expected volume of devices is high then mask programmable ROM is used. This type of ROM is mask programmed prior to packaging of the die. The information to be programmed must be highly stable and not subject to revision since changes in the programmed information require a mask change. The benefits of using mask programmed ROM relate to cost and time savings for high volume, mature products. Other types of ROM are available for products that do not sustain production volumes or code stability sufficient to justify mask programmed ROM.
Programmable Read Only Memory (PROM) allows the device manufacturer to program the embedded code. This allows for revisions in the code but still does not allow for modification or erasure of the ROM once it has been programmed. Devices that have been programmed with an out of date code revision will either need to be used with the out of date code revision or will need to be discarded.
Erasable Programmable Read Only Memory (EPROM) provides the ability to completely erase a programmed part. Erasure of an EPROM is accomplished by exposing the die to ultraviolet (UV) light for a predetermined period of time. The die can be exposed to the UV light through a transparent window on the EPROM package. Once erased, the EPROM can be reprogrammed. EPROMs are typically only used for engineering development where the expected number of code revisions is high. The limitations on the package type that can accommodate the transparent window contribute to the much higher price of an EPROM when compared to a PROM. Although the EPROM can be erased and reprogrammed, modifications to the code must be done on a complete chip basis. Even changes to a single bit within the code require complete erasure and reprogramming. This limitation, along with the requirement for a UV light for erasure confine the task of updating EPROMs to original equipment manufacturers (OEMs).
A device that allows for selective content erasure and reprogramming is the Electrically Erasable Programmable Read Only Memory (EEPROM). Conventional EEPROM allows for data to be updated in place. That is, a particular data location can be erased and new data overwritten in the same location. Data can be read from an EEPROM quickly but the write cycle of the conventional EEPROM can be orders of magnitude longer than the read time. Another disadvantage of using a conventional EEPROM arises from the inherent structure of the conventional EEPROM cell. The structure of a conventional EEPROM cell requires more transistors than in a standard PROM. The increased structure results in reduced memory capacity and increased cost. These disadvantages make usage of conventional EEPROM prohibitive in most consumer electronics applications.
Random Access Memory (RAM) represents another alternate means for storage. RAM allows for selective data reads and writes. Read and write can be performed on a byte basis. No erase cycle is required before writing new data to a previously written byte. Moreover, unlike the EEPROM, the read and write cycle times of the RAM are nearly identical. The density and capacity of RAM is comparable to ROM. The major disadvantage in using RAM is the volatile nature of the stored data. Information stored in RAM is lost whenever the RAM powers down. This is in contrast to ROM, which is nonvolatile memory, where the contents of memory remain even after the IC has been power cycled. In order to retain the contents of RAM, power must be maintained on the chip at all times. This requires a battery back up to the normal power supply. If the battery back up fails when the power supply is de-energized the contents of RAM will be lost. For this reason RAM is not used for embedded code and is used only for dynamic memory. RAM used for embedded code would be susceptible to loss of battery power and power supply glitches. Furthermore, if RAM were used for embedded code, battery operated devices such as cellular telephones would have diminished battery life due to the constant power requirements of the RAM. When RAM is used for dynamic memory the system does not care if the contents are lost after a power cycle. This alleviates the need for battery back up. However, the cost of RAM is higher than the cost of ROM.
Another storage alternative is sectored EEPROM commonly referred to as FLASH memory. Sectored EEPROM is a nonvolatile storage device that allows read and write on a byte basis. Unlike RAM, in sectored EEPROM an erase operation must be performed before rewriting over a previously written byte. However, data erasure cannot be performed on a byte basis. Erasure can only be performed on a sector basis, where the size of the sector is defined by the particular memory device chosen. The size of an erasable sector is always larger than one byte and can be on the order of 64 Kbytes. However, the number of erase cycles is not unlimited, but is bounded by a maximum cycle life. A typical recommended erase cycle life for sectored EEPROM is 100,000 cycles. Therefore, one would not use sectored EEPROM for applications requiring greater than 100,000 erase cycles over the anticipated device lifetime. Sectored EEPROM has advantages over the other types of rewriteable memory in applications that require fewer than 100,000 erase and rewrite cycles. Sectored EEPROM is preferred over any type of RAM for embedded code applications because sectored EEPROM is nonvolatile. Sectored EEPROM is preferable over EPROM because of sectored EEPROM""s ability to rewrite portions of memory in circuit. Sectored EEPROM also does not require the UV light for chip erasure. Sectored EEPROM is preferable over conventional EEPROM, which has comparable rewrite limitations, because of the lower cost and higher density of sectored EEPROM devices. Sectored EEPROMs are used in portable electronic devices for the nonvolatile storage of user configurable data.
Data stored in sectored EEPROM is often formatted to conform to a file system. The file format convention is partially driven by the sector sized erase cycle. Data is not memory mapped to a particular location since data in sectored EEPROM cannot be rewritten in place. The additional software overhead results in dramatically increased memory access times. The access time is further increased in multi-tasking systems. Nonvolatile memory access in a multi-tasking system may be preempted by a higher priority task. Preemption requires the lower priority task to wait for the completion of the higher priority task before proceeding. When the software overhead is included in the calculation of access times, the time to access data from sectored EEPROM may be more than 1000 to 10,000 times slower than the access time to data stored in RAM devices.
Long access times present user interface problems. In a portable electronic device such as a wireless phone, nonvolatile user configurable data is often stored in sectored EEPROM. The user interface is enhanced if access to the phone book data appears to occur instantaneously. Data retrieval from sectored EEPROM results in a slow user response when a user enters a phone number to compare against the entries in the phone book. This is due to the software overhead in dealing with the file system that must be initiated in order to retrieve any data from sectored EEPROM. The long access time delay presents a serious problem in real time systems where data retrieval must occur within some predefined window of time.
One solution to the slow access times of sectored EEPROM, or any other nonvolatile memory, is to transfer all data from nonvolatile data records to RAM. The data records could be transferred from nonvolatile RAM upon device power up. Then all the data can quickly be retrieved from RAM. This greatly enhances the user interface. However, this solution presents considerable cost and space disadvantages. Additional RAM is required that redundantly stores the contents of the nonvolatile memory merely to enhance the user interface. What is required is a method and apparatus for reducing the amount of RAM required to maintain a fast user interface when accessing data stored in nonvolatile memory.
The present invention is a novel and improved method and apparatus for reducing the amount of RAM required to support fast data retrieval from slower non-volatile memory. The use of RAM instead of nonvolatile memory greatly decreases data search time. RAM access is orders of magnitude faster than nonvolatile memory access due to software overhead that must be performed each time nonvolatile memory is accessed.
A collection of data records can be saved in nonvolatile memory. Access to the nonvolatile data records is slowed because of the software overhead associated with nonvolatile memory access. The present invention can be used to greatly enhance searches of data records saved in nonvolatile memory. When data records saved in nonvolatile memory must be searched, numerous accesses to the nonvolatile memory are typically required. The present invention reduces the number of accesses to the nonvolatile data records by saving a series of calculated tag values in predetermined locations in RAM. Searches for data records saved in nonvolatile memory are then performed by searching through the predetermined RAM locations for corresponding tag values then looking up the nonvolatile data record if a matching tag value is found. Searching for matching tag values in RAM reduces to one the typical number of nonvolatile memory accesses required to search for a matching data record. This contrasts with the numerous nonvolatile record retrievals and comparisons required in a conventional search of nonvolatile data records.
A predetermined number of memory locations are allocated in RAM corresponding to the number of data records saved in the nonvolatile memory. Each memory location allocated in RAM need not be large enough to hold the data record saved in nonvolatile memory. In the preferred embodiment two bytes of RAM are allocated for each data record location in nonvolatile memory. The nonvolatile data record may be arbitrarily long. A tag function H(x) is defined to map each nonvolatile record into a corresponding tag value. The tag function H(x) need not provide a 1:1 mapping of data records to tag values. A 1:1 mapping of data records to tag values minimizes the number of nonvolatile memory accesses to one nonvolatile record access per data record search.
The predetermined RAM locations hold tag values determined from contents of the corresponding nonvolatile data records. When a search for a particular data record is required a tag value is calculated for the searched record. If the searched record is designated y, the tag value H(y) is calculated. The tag value H(y) is then compared to all tag values stored in the predetermined RAM locations. This step is performed very quickly due to the fast access capabilities of RAM. If a matching tag value in RAM i s found the corresponding nonvolatile memory location is identified as that location that corresponds to the particular RAM location. The contents of the nonvolatile data record are retrieved and compared to the searched record. I f the two match then the search is complete. If the retrieved nonvolatile memory record and the searched record are not identical matches the remaining tag values in RAM are searched for additional matches to the tag value calculated for the searched record. The search continues until an identical match is found or the end of the RAM tag value s is reached.
The present invention provides an enormous decrease in the amount of time that it takes to search the data records since the majority of the search is performed using the RAM tag tables. The nonvolatile memory records a re only accessed when a tag value match is found. For the majority of the searches only one nonvolatile memory access will be required. The time savings allow for an enhanced user interface while the reduction in RAM provides reduced hardware cost.